#!/usr/bin/env python
# encoding: utf-8
"""
@author: shura
@position: saber
@contact: 2209032305@qq.com
@file: mid.py
@time: 2018/11/28 9:40
@desc:
"""
class Interval:
    def __init__(self, s=0, e=0):
        self.start = s
        self.end = e


class Solution:
    def spiralOrder(self, matrix):
        """
        54 旋转矩阵
        题目描述
        给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        res = []
        while matrix:
            res = res + matrix.pop(0)
            matrix = list(map(list, zip(*matrix)))[::-1]
        return res

    def canJump(self, nums):
        """
        55 跳跃游戏
        给定一个非负整数数组，你最初位于数组的第一个位置。
        数组中的每个元素代表你在该位置可以跳跃的最大长度。
        判断你是否能够到达最后一个位置。
        输入: [2,3,1,1,4]
        输出: true
        解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。
        :type nums: List[int]
        :rtype: bool
        """
        # 贪心法 从前往后遍历
        end = 0
        for i in range(len(nums)-1):
            if i <= end and i + nums[i] > end:
                end = nums[i] + i
        return end >= len(nums)-1

    def merge(self, intervals):
        """
        56 区间合并
        输入: [[1,3],[2,6],[8,10],[15,18]]
        输出: [[1,6],[8,10],[15,18]]
        解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
        :type intervals: List[Interval]
        :rtype: List[Interval]
        """
        res = []
        for i in sorted(intervals, key=lambda i: i.start):
            if res and i.start <= res[-1].end:
                res[-1].end = max(res[-1].end, i.end)
            else:
                res += i,
        return res


if __name__ == '__main__':
    s = Solution()
    a1 = Interval(2,3)
    a2 = Interval(4,5)
    a3 = Interval(6,7)
    a4 = Interval(8,9)
    a5 = Interval(1,10)
    a = [a1,a2,a3,a4,a5]
    print(s.merge(a))
